/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
 * 算法导论中的最大子数组问题
 * 可以用分治,也可以用动态规划
 */
package dataStructure.Test121买卖股票的最佳时机;

public class Solution {
    public int maxProfit(int[] prices) {
        //m[i]:截止到第i天能获得的最大利润
        int[] m = new int[prices.length];
        int minPrice = prices[0];
        for (int i = 0; i < prices.length; i++) {
            if (i == 0)
                m[i] = 0;
            else {
                if (prices[i] < minPrice)
                    minPrice = prices[i];
                m[i] = Math.max(m[i - 1], prices[i] - minPrice);
            }
        }
        return m[prices.length - 1];
    }
    public int maxProfit2(int[] prices) {
        int length = prices.length;
        //m[i]:截止到第i天能获得的最大利润
        int[] m = new int[length];
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
                if (prices[i] < minPrice)
                    minPrice = prices[i];
                m[i] = Math.max(m[i - 1], prices[i] - minPrice);
        }
        return m[length - 1];
    }
}
